open Ast
open Printf
open Classes
open Game

module NameMap = Map.Make(struct
    type t = string
    let compare x y = Pervasives.compare x y
end)

module StringMap = Map.Make(String);;

let mymap = new gamemap;;
let pointMap = ref StringMap.empty;;

let avail_x = ref 0;;
let avail_y = ref 0;;
let num_items = ref 0;;
let gift_colors = [|(1.,0.5,0.5) ; (0.5,0.5,1.) ; (1.,0.,1.) ; (0.8,0.8,0.6)|];

exception ReturnException of myType * myType NameMap.t

(* Initiate variable *)
let init t = 
  match t with
    "int" -> Int(0)
    | "bool" -> Bool(false)
    | "string" -> String("")
    | "map" -> Map({ pacman= {speed=5;  status="normal";  p_point={x=1; y=1};  remaining_time=0}; list_item=[]; width=1500 ; height=1500})
    | "player" -> Player({speed=5;  status="normal";  p_point={x=1; y=1} ;remaining_time=0})
    | "item" -> Item({i_type=0; duration=0;i_point={x=0; y=0}; color=(1.,1.,1.); level=0})    
    | "point" -> Point({x=0; y=0})   
    | _ -> Int(0)


(* Main entry point: run a program *)
let run (vars, funcs) =
    (* Put function declarations in a symbol table *)
    let func_decls = List.fold_left
        (fun funcs fdecl -> NameMap.add fdecl.fname fdecl funcs)
        NameMap.empty funcs
    in
    
    (* Invoke a function and return an updated global symbol table *)
    let rec call fdecl actuals globals =
    
    (* Evaluate an expression and return (value, updated environment) *)
    let rec eval env = function
            Integer(i) -> Int i, env

        | GameType(i) -> 
            (match i with
              "_EASY" -> Int 0, env
            | "_NORMAL" -> Int 1, env
            | "_HARD" -> Int 2, env
            | "_GHOST" -> Int 3, env
            | "_BARRIER" -> Int 4, env    
            | "_GIFT" -> Int 5, env    
            | "_GIFT_SPEEDUP" -> Int 6, env    
            | "_GIFT_SLOWDOWN" -> Int 7, env    
            | "_GIFT_KILLER" -> Int 8, env    
            | "_GIFT_SCORE" -> Int 9, env            
            | _ -> raise (Failure ("Invalid game type: " ^ i ^ ".")))

        | NoExpr ->  Int 1, env 
	(* String *)
        | Strings(var) -> String var, env            
	(* Identifier *)
        | Id(var) ->
            let locals, globals = env in
            if NameMap.mem var locals then
                (NameMap.find var locals), env
            else if NameMap.mem var globals then
                (NameMap.find var globals), env
            else raise (Failure ("Undeclared identifier: " ^ var))
	(* Assign value to member *)
        | Member(var, i) ->             
            let v, env = eval env (Id var) in
                let vType = getType v in
                (match vType with 
                  | "player" -> 
                    (match i with
                      | "p_point" -> Point (getPlayer v).p_point
                      | _ -> raise (Failure ("Invalid member of Player: " ^ i)))
                  | "item" ->
                    (match i with
                        "i_type" -> Int (getItem v).i_type  
                      | "duration" -> Int (getItem v).duration
                      | "i_point" -> Point (getItem v).i_point
                      | "level" -> Int (getItem v).level     
                      | _ -> raise (Failure ("Invalid member of Item: " ^ i)))
                  | "point" -> 
                    (match i with
                        "x" -> Int (getPoint v).x
                      | "y" -> Int (getPoint v).y
                      | _ -> raise (Failure ("Invalid member of Point: " ^ i)))                            
                  | _ -> raise (Failure ("Cannot access " ^ var ^ "." ^ i))), env   
	(* Binary operator *)             
        | BinOp(e1, op, e2) -> 
            let v1, env = eval env e1 in
            let v2, env = eval env e2 in
            let v1Type = getType v1 in
            let v2Type = getType v2 in
            if v1Type = v2Type then
                (match op with
                    Add -> 
                        if v1Type = "int" then
                             Int (getInt v1 + getInt v2)
			else if v1Type = "point" then
                             if ((getPoint v1).x + (getPoint v2).x)>=1 && ((getPoint v1).x + (getPoint v2).x)<=13
				&& ((getPoint v1).y + (getPoint v2).y)>=1 && ((getPoint v1).y + (getPoint v2).y)<=13 then
                                 Point({x=((getPoint v1).x + (getPoint v2).x); y=((getPoint v1).y + (getPoint v2).y)})
                             else    raise (Failure ("Out of bound: The value of point.x and point.y should be between 1-13"))
                        else raise (Failure ("Incorrect data type: " ^ v1Type ^ " + " ^ v2Type))
                    | Sub -> 
                        if v1Type = "int" then
                             Int (getInt v1 - getInt v2)
			else if v1Type = "point" then
                            if ((getPoint v1).x - (getPoint v2).x)>=1 && ((getPoint v1).x - (getPoint v2).x)<=13
				&& ((getPoint v1).y - (getPoint v2).y)>=1 && ((getPoint v1).y - (getPoint v2).y)<=13 then
                                Point({x=((getPoint v1).x - (getPoint v2).x); y=((getPoint v1).y - (getPoint v2).y)})
                            else    raise (Failure ("Out of bound: The value of point.x and point.y should be between 1-13")) 
                        else raise (Failure ("Incorrect data type: " ^ v1Type ^ " - " ^ v2Type))     
                    | Mult ->
                        if v1Type = "int" then
                             Int (getInt v1 * getInt v2)
			else if v1Type = "point" then
                            if ((getPoint v1).x * (getPoint v2).x)>=1 && ((getPoint v1).x * (getPoint v2).x)<=13
				&& ((getPoint v1).y * (getPoint v2).y)>=1 && ((getPoint v1).y * (getPoint v2).y)<=13 then
                                Point({x=((getPoint v1).x * (getPoint v2).x); y=((getPoint v1).y * (getPoint v2).y)})
                            else    raise (Failure ("Out of bound: The value of point.x and point.y should be between 1-13"))                            
                        else raise (Failure ("Incorrect data type: " ^ v1Type ^ " * " ^ v2Type))     
                    | Div ->
                        if v1Type = "int" then
                             Int (getInt v1 / getInt v2)
			else if v1Type = "point" then
                            if ((getPoint v1).x / (getPoint v2).x)>=1 && ((getPoint v1).x / (getPoint v2).x)<=13
				&& ((getPoint v1).y / (getPoint v2).y)>=1 && ((getPoint v1).y / (getPoint v2).y)<=13 then
                                Point({x=((getPoint v1).x / (getPoint v2).x); y=((getPoint v1).y / (getPoint v2).y)})
                            else    raise (Failure ("Out of bound: The value of point.x and point.y should be between 1-13"))  
                        else raise (Failure ("Incorrect data type: " ^ v1Type ^ " / " ^ v2Type))     
                    | Mod -> 
                        if v1Type = "int" then
                             Int (getInt v1 mod getInt v2)
                        else raise (Failure ("Incorrect data type: " ^ v1Type ^ " % " ^ v2Type))     
                    | And -> 
                        if v1Type = "bool" then
                             Bool (getBool v1 && getBool v2)
                        else raise (Failure ("Incorrect data type: " ^ v1Type ^ " && " ^ v2Type))       
                    | Or -> 
                        if v1Type = "bool" then
                             Bool (getBool v1 || getBool v2)
                        else raise (Failure ("Incorrect data type: " ^ v1Type ^ " || " ^ v2Type))                      
                    | Eq -> 
                        if v1Type = "int" then
                               Bool (getInt v1 = getInt v2)
                        else if v1Type = "map" then
                             Bool (getMap v1 = getMap v2)
                        else if v1Type = "player" then
                             Bool (getPlayer v1 = getPlayer v2)
                        else if v1Type = "item" then
                             Bool (getItem v1 = getItem v2)        
                        else if v1Type = "point" then
                             Bool (getPoint v1 = getPoint v2)
                        else raise (Failure ("Incorrect data type: " ^ v1Type ^ " == " ^ v2Type))                          
                    | NEq -> 
                        if v1Type = "int" then
                               Bool (getInt v1 != getInt v2) 
                        else if v1Type = "map" then
                             Bool (getMap v1 != getMap v2)
                        else if v1Type = "player" then
                             Bool (getPlayer v1 != getPlayer v2)
                        else if v1Type = "item" then
                             Bool (getItem v1 != getItem v2)        
                        else if v1Type = "point" then
                             Bool (getPoint v1 != getPoint v2)
                        else raise (Failure ("Incorrect data type: " ^ v1Type ^ " == " ^ v2Type)) 
                    | Less ->
                        if v1Type = "int" then
                               Bool (getInt v1 < getInt v2)
                        else raise (Failure ("Cannot compare " ^ v1Type ^ " < " ^ v2Type))                    
                    | LEq ->
                        if v1Type = "int" then
                               Bool (getInt v1 <= getInt v2)
                        else raise (Failure ("Cannot compare: " ^ v1Type ^ " <= " ^ v2Type))               
                    | Greater -> 
                        if v1Type = "int" then
                               Bool (getInt v1 > getInt v2)    
                        else raise (Failure ("Cannot compare: " ^ v1Type ^ " > " ^ v2Type))          
                    | GEq -> 
                        if v1Type = "int" then
                               Bool (getInt v1 >= getInt v2)    
                        else raise (Failure ("Cannot compare: " ^ v1Type ^ " >= " ^ v2Type))), env
            else raise (Failure ("Data type mismatch : " ^ v1Type ^ " and " ^ v2Type))
          (* Assignment *)
        | Assign(var, e) ->
            let var1, env = eval env var in
            let e1, (locals, globals) = eval env e in
            let v1Info =   
                match var with
                        Id (i) -> ("id", (i, ""))
                    | Strings(i) -> ("strings", (i, ""))
                    | Member(i, j) -> ("member", (i, j))
                    | _ -> raise (Failure ("Left side must be an identifier or a member")) in         
                let v1IdType = fst v1Info in
                let v1Name = snd v1Info in
                let v1Type = (* ("map", "locals") *)
                    (if NameMap.mem (fst v1Name) locals then
                        (getType (NameMap.find (fst v1Name) locals), "locals")
                    else if NameMap.mem (fst v1Name) globals then
                        (getType (NameMap.find (fst v1Name) globals), "globals")
                    else raise (Failure ("Undeclared identifier: " ^ fst v1Name)))                      
                in  
                let v1RetType = getType var1 in 
                let e1Type = getType e1 in     
                if v1RetType = e1Type then
                     match v1RetType with
                        "int" ->
                            if v1IdType = "id" then
                                (if snd v1Type = "locals" then
                                    e1, (NameMap.add (fst v1Name) e1 locals, globals)
                                else if snd v1Type = "globals" then
                                    e1, (locals, NameMap.add (fst v1Name) e1 globals)
                                else raise (Failure ("Fatal error")))
                            else if v1IdType = "member" then
                                if fst v1Type = "item"  then
                                    if snd v1Name = "i_type" then
                                        if getInt e1 = 3 || getInt e1 = 4  || getInt e1 = 5then
                                            if snd v1Type = "locals" then
                                                e1, (
                                                    ((getItem (NameMap.find (fst v1Name) locals)).i_type <- getInt e1); 
                                                    (locals, globals))
                                            else if snd v1Type = "globals" then
                                                e1, (
                                                    ((getItem (NameMap.find (fst v1Name) globals)).i_type <- getInt e1); 
                                                    (locals, globals))            
                                            else raise (Failure ("Fatal error"))
                                        else raise (Failure ("Invalid value of i_type: " ^ string_of_int (getInt e1) ^ ". i_type must be _GHOST, _BARRIER, or _GIFT."))
                                    else if snd v1Name = "duration" then
                                        if getInt e1 >= 100 && getInt e1 <= 500 then
                                            if snd v1Type = "locals" then
                                                e1, (
                                                    ((getItem (NameMap.find (fst v1Name) locals)).duration <- getInt e1); 
                                                    (locals, globals))
                                            else if snd v1Type = "globals" then
                                                e1, (
                                                    ((getItem (NameMap.find (fst v1Name) globals)).duration <- getInt e1); 
                                                    (locals, globals))            
                                            else raise (Failure ("Fatal error"))
                                        else raise (Failure ("Invalid value of duration: " ^ string_of_int (getInt e1) ^ ". Duration must be between 100-500."))                

                                    else if snd v1Name = "level" then
                                        if (getItem (NameMap.find (fst v1Name) locals)).i_type = 3 then
                                            if getInt e1 = 0 || getInt e1 = 1 || getInt e1 = 2 then
                                                if snd v1Type = "locals" then
                                                    e1, (
                                                        ((getItem (NameMap.find (fst v1Name) locals)).level <- getInt e1); 
                                                        (locals, globals))
                                                else if snd v1Type = "globals" then
                                                    e1, (
                                                        ((getItem (NameMap.find (fst v1Name) globals)).level <- getInt e1); 
                                                        (locals, globals))            
                                                else raise (Failure ("Fatal error"))                                
                                            else raise (Failure ("Invalid value of level: " ^ string_of_int (getInt e1) ^ ". level must be _EASY(0), _MEDIAN(1), or _HARD(2)"))                                

                                        else if (getItem (NameMap.find (fst v1Name) locals)).i_type = 5 then
                                            if getInt e1 = 6 || getInt e1 = 7 || getInt e1 = 8 || getInt e1 = 9 then
                                                if snd v1Type = "locals" then
                                                    e1, (
                                                        ((getItem (NameMap.find (fst v1Name) locals)).level <- ((getInt e1)-5));
                                                        ((getItem (NameMap.find (fst v1Name) locals)).color <- gift_colors.(((getInt e1)-6))); 
                                                        (locals, globals))
                                                else if snd v1Type = "globals" then
                                                    e1, (
                                                        ((getItem (NameMap.find (fst v1Name) globals)).level <- ((getInt e1)-5));
                                                        ((getItem (NameMap.find (fst v1Name) locals)).color <- gift_colors.(((getInt e1)-6))); 
                                                        (locals, globals))            
                                                else raise (Failure ("Fatal error"))                                
                                            else raise (Failure ("Invalid value of level: " ^ string_of_int (getInt e1) ^ ". Level must be _GIFT_SPEEDUP, _GIFT_SLOWDOWN, _GIFT_KILLER, _GIFT_SCORE"))
                                        else raise (Failure ("Invalid value of level: Level of this item shouldn't be used."))
                                    else raise (Failure ("Fatal error"))
                                else if fst v1Type = "point" then
                                    if snd v1Name = "x" then
                                        if getInt e1 >= 1 && getInt e1 <= 13 then
                                            if snd v1Type = "locals" then
                                                e1, (
                                                    ((getPoint (NameMap.find (fst v1Name) locals)).x <- getInt e1); 
                                                    (locals, globals))
                                            else if snd v1Type = "globals" then
                                                e1, (
                                                    ((getPoint (NameMap.find (fst v1Name) globals)).x <- getInt e1); 
                                                    (locals, globals))            
                                            else raise (Failure ("Fatal error"))
                                        else raise (Failure ("invalid point x: " ^ string_of_int (getInt e1) ^ ". x must be between 1-13."))
                                else if snd v1Name = "y" then
                                        if getInt e1 >= 1 && getInt e1 <= 13 then
                                            if snd v1Type = "locals" then
                                                e1, (
                                                    ((getPoint (NameMap.find (fst v1Name) locals)).y <- getInt e1); 
                                                    (locals, globals))
                                            else if snd v1Type = "globals" then
                                                e1, (
                                                    ((getPoint (NameMap.find (fst v1Name) globals)).y <- getInt e1);
                                                    (locals, globals))            
                                            else raise (Failure ("Fatal error"))
                                        else raise (Failure ("invalid point y: " ^ string_of_int (getInt e1) ^ ". y must be between 1-13."))
                                    else raise (Failure ("Fatal error"))
                                else raise (Failure ("Cannot assign value to: " ^ fst v1Type ^ "." ^ snd v1Name)) 
                            else raise (Failure ("Cannot assign value to: " ^ fst v1Type)) 
                    | "string" ->
                        if v1IdType = "id" then
                            (if snd v1Type = "locals" then
                                e1, (NameMap.add (fst v1Name) e1 locals, globals)
                            else if snd v1Type = "globals" then
                                e1, (locals, NameMap.add (fst v1Name) e1 globals)
                            else raise (Failure ("Fatal error")))                        
                        else raise (Failure ("Cannot assign to: " ^ fst v1Type)) 

                    | "point" ->
                        if v1IdType = "id" then
                            (if snd v1Type = "locals" then
                                e1, (NameMap.add (fst v1Name) e1 locals, globals)
                            else if snd v1Type = "globals" then
                                e1, (locals, NameMap.add (fst v1Name) e1 globals)
                            else raise (Failure ("Fatal error")))
                        else if v1IdType = "member" then
                            if fst v1Type = "player" then
                                if snd v1Name = "p_point" then
                                    if getType e1 = "point" then
                                        if snd v1Type = "locals" then
                                            e1, (
                                                ((getPlayer (NameMap.find (fst v1Name) locals)).p_point.x <- (getPoint e1).x);
                                                ((getPlayer (NameMap.find (fst v1Name) locals)).p_point.y <- (getPoint e1).y); 
                                                (locals, globals))
                                        else if snd v1Type = "globals" then
                                            e1, (
                                                ((getPlayer (NameMap.find (fst v1Name) globals)).p_point.x <- (getPoint e1).x);
                                                ((getPlayer (NameMap.find (fst v1Name) globals)).p_point.y <- (getPoint e1).y);
                                                (locals, globals))            
                                        else raise (Failure ("Fatal error"))
                                    else raise (Failure ("Invalid value of i_point: " ^ getString e1 ^ ". Type of the argument should be point."))
                                else raise (Failure ("Fatal error"))                                
                            else if fst v1Type = "item" then
                                if snd v1Name = "i_point" then
                                    if getType e1 = "point" then
                                        if snd v1Type = "locals" then
                                            e1, (
                                                ((getItem (NameMap.find (fst v1Name) locals)).i_point.x <- (getPoint e1).x);
                                                ((getItem (NameMap.find (fst v1Name) locals)).i_point.y <- (getPoint e1).y); 
                                                (locals, globals))
                                        else if snd v1Type = "globals" then
                                            e1, (
                                                ((getItem (NameMap.find (fst v1Name) locals)).i_point.x <- (getPoint e1).x);
                                                ((getItem (NameMap.find (fst v1Name) locals)).i_point.y <- (getPoint e1).y); 
                                                (locals, globals))            
                                        else raise (Failure ("Fatal error"))
                                    else raise (Failure ("Invalid value of i_point: " ^ getString e1 ^ ". Type of argument should be point."))
                                else raise (Failure ("Fatal error"))                            
                            else raise (Failure ("Cannot assign value to: " ^ fst v1Type)) 
                        else raise (Failure ("Cannot assign value to: " ^ fst v1Type)) 
                    | _ -> (* player, point, point *)
                        if v1IdType = "id" then
                            (if snd v1Type = "locals" then
                                e1, (NameMap.add (fst v1Name) e1 locals, globals)
                            else if snd v1Type = "globals" then
                                e1, (locals, NameMap.add (fst v1Name) e1 globals)
                            else raise (Failure ("Fatal error")))
                        else raise (Failure ("Cannot assign value to: " ^ fst v1Type))              
                else if v1IdType = "id" then
                       raise (Failure ("Cannot assign: " ^ fst v1Type ^ " = " ^ e1Type))
                else if v1IdType = "member" then
                       raise (Failure ("Cannot assign: " ^ v1RetType ^ " = " ^ e1Type))
                else raise (Failure ("Fatal error"))
        | Not(var) ->
            let vnew, envnew = eval env var in 
                if getType vnew = "bool" then
                    Bool(not (getBool vnew)), envnew  
                else raise (Failure ("Data type mismatch: " ^ getType vnew))

    (* built-in sfunction setPlayer(player) *)
    | Call("setPlayer", [e]) ->
        let v, env = eval env e in
        let v1Info =   
            match e with
                Id (i) -> ("id", (i, ""))
            | _ -> raise (Failure ("left side must be an identifier or a member")) in         
        let v1Name = snd v1Info in
            (if getType v = "player"  then
                let pacman = getPlayer(v) in
                (if((StringMap.mem (string_of_int(pacman.p_point.x) ^ "," ^ string_of_int(pacman.p_point.y)) !pointMap) = false) then
                    ignore(                
                        let tmp = new player in                    
                        tmp#setSpeed 5;
                        tmp#getPoint#setX (pacman.p_point.x*100+50);
                        tmp#getPoint#setY (pacman.p_point.y*100+50);
                        mymap#setPlayer tmp;                    
                        pointMap := StringMap.add (string_of_int(pacman.p_point.x) ^ "," ^ string_of_int(pacman.p_point.y)) v1Name !pointMap;
                        num_items := !num_items +1;
                    )  
                else
                    raise (Failure ("This point has been used (setPlayer(player))")));
            else
                raise (Failure ("type mismatch: !" ^ getType v)));
          Int(0), env   
   
    (* built-in function addGhost(item) *)
    | Call("addGhost", [e]) ->
        let v, env = eval env e in
        let v1Info =   
                match e with
                       Id (i) -> ("id", (i, ""))
                     | _ -> raise (Failure ("Left side must be an identifier or a member")) in         
        let v1Name = snd v1Info in
            (if getType v = "item"  then
                let ghost = getItem(v) in
                    (if((StringMap.mem (string_of_int(ghost.i_point.x) ^ "," ^ string_of_int(ghost.i_point.y)) !pointMap) = false) then
                        ignore(
                            if ghost.i_type = 3 then            
                            let tmp = new item in                    
                            tmp#setSpeed 5;
                            tmp#setType 1;
                            tmp#getPoint#setX (ghost.i_point.x*100+50);
                            tmp#getPoint#setY (ghost.i_point.y*100+50);
                            tmp#setLevel ghost.level;    
                            tmp#setColor ((Random.float 1.), (Random.float 1.), (Random.float 1.));
                            tmp#setRadius 0.49;
                            mymap#addGhost tmp;
                            pointMap := StringMap.add (string_of_int(ghost.i_point.x) ^ "," ^ string_of_int(ghost.i_point.y)) v1Name !pointMap;
                            num_items := !num_items +1;
                        else
                            raise (Failure ("Data type mismatch: This item is not GHOST"));
                        )
                    else
                        raise (Failure ("This point has been used (addGhost(Item))")));
            else
                raise (Failure ("Data type mismatch: " ^ getType v)));
        Int(0), env   
   
    (* built-in function addBarrier(item) *)
    | Call("addBarrier", [e]) ->
        let v, env = eval env e in
        let v1Info =   
            match e with
                Id (i) -> ("id", (i, ""))
            | _ -> raise (Failure ("Left side must be an identifier or member access")) in         
        let v1Name = snd v1Info in
            (if getType v = "item"  then
                let barrier = getItem(v) in
                    (if((StringMap.mem (string_of_int(barrier.i_point.x) ^ "," ^ string_of_int(barrier.i_point.y)) !pointMap) = false) then
                        ignore(                
                        if barrier.i_type = 4 then            
                            let tmp = new item in
                            tmp#setType 0;
                            tmp#getPoint#setX (barrier.i_point.x);
                            tmp#getPoint#setY (barrier.i_point.y);
                            mymap#addBar tmp;                    
                            pointMap := StringMap.add (string_of_int(barrier.i_point.x) ^ "," ^ string_of_int(barrier.i_point.y)) v1Name !pointMap;
                            num_items := !num_items +1;
                        else
                            raise (Failure ("Data type mismatch: This item is not BARRIER")))            
                    else
                        raise (Failure ("This point has been used (addBarrier(Item))")));
            else
                raise (Failure ("Data type mismatch: " ^ getType v)));
        Int(0), env 

    (* built-in function addBarrier(item) *)
    | Call("addBarrier", [e1 ; e2]) ->
        let v1, env = eval env e1 in
        let v2, env = eval env e2 in      
            (if getType v1 = "int" && getType v2 = "int" then
                (if getInt v1 >=1 && getInt v1 <=13 && getInt v2 >=1 && getInt v2 <=13 then
                    ignore(
                    if ((StringMap.mem (string_of_int(getInt v1) ^ "," ^ string_of_int(getInt v2)) !pointMap) = false) then                                            
                        let tmp = new item in
                        tmp#setType 0;
                        tmp#getPoint#setX (getInt v1);
                        tmp#getPoint#setY (getInt v2);
                        mymap#addBar tmp;    
                        pointMap := StringMap.add (string_of_int((getInt v1)) ^ "," ^ string_of_int((getInt v2))) ("barrier_tmp","") !pointMap;        
                        num_items := !num_items +1;
                    else
                        raise (Failure ("This point has been used (addBarrier(int x,int y))")))
                else
                    raise (Failure ("Value error: The value should be between 1 to 13. ( arg1=" ^ string_of_int(getInt v1) ^ ", arg2=" ^ string_of_int(getInt v2) ^ ".) ")))
            else
                raise (Failure ("Data type mismatch: arg1=" ^ getType v1 ^ ", arg2=" ^ getType v2 ^ ".")));

        Int(0), env

    (* built-in function addGift(item) *)
    | Call("addGift", [e]) ->
        let v, env = eval env e in
        let v1Info =   
            match e with
                Id (i) -> ("id", (i, ""))
            | _ -> raise (Failure ("left side of assignment must be an identifier or member access")) in         
        let v1Name = snd v1Info in
            (if getType v = "item"  then
                let gift = getItem(v) in
                    (if((StringMap.mem (string_of_int(gift.i_point.x) ^ "," ^ string_of_int(gift.i_point.y)) !pointMap) = false) then
                        ignore(
                        if gift.i_type = 5 then            
                            let tmp = new item in
                            tmp#setType 2;
                            tmp#getPoint#setX (gift.i_point.x*100+50);
                            tmp#getPoint#setY (gift.i_point.y*100+50);
                            tmp#setColor gift.color;
                            tmp#setLevel gift.level;
                            tmp#setRadius 0.35;
                            tmp#setDuration 200;
                            mymap#addGift tmp;                    
                            pointMap := StringMap.add (string_of_int(gift.i_point.x) ^ "," ^ string_of_int(gift.i_point.y)) v1Name !pointMap;
                            num_items := !num_items +1;
                        else
                            raise (Failure ("Data type mismatch: This item is not GIFT")))            
                    else
                        raise (Failure ("This point has been used (addGift)")));
            else
                raise (Failure ("Data type mismatch: " ^ getType v)));
          Int(0), env 
         
    (* built-in function getMapWidth() *)
    | Call("getMapWidth", []) ->
        Int(15), env
         
    (* built-in function getMapHeight() *)
    | Call("getMapHeight", []) ->
        Int(15), env

    (* built-in function play() *)
    | Call("play", []) ->
        show_pacman  mymap;
        Int(0), env

    (* built-in function getMapItemName(point) *)
    | Call("getMapItemName", [e]) ->
        let v, env = eval env e in
            (if getType v = "point"  then
                let point = getPoint(v) in            
                    (if((StringMap.mem (string_of_int(point.x) ^ "," ^ string_of_int(point.y)) !pointMap) = true) then    
                        String(fst (StringMap.find (string_of_int(point.x) ^ "," ^ string_of_int(point.y)) !pointMap)),env 
                    else
                        String(""),env)
            else
                raise (Failure ("Data type mismatch: " ^ getType v)));

    (* built-in function isPointAvailable(point) *)
    | Call("isPointAvailable", [e]) ->
        let v, env = eval env e in
            (if getType v = "point"  then
                let point = getPoint(v) in            
                    (if((StringMap.mem (string_of_int(point.x) ^ "," ^ string_of_int(point.y)) !pointMap) = false) then    
                        Bool(true),env 
                    else
                        Bool(false),env)
            else
                raise (Failure ("Data type mismatch: " ^ getType v)));

    (* built-in function getAvailablePoint(point) *)
    | Call("getAvailablePoint", []) ->        
        if !num_items < 169 then 
            let r = ref 1 in
                while !r > 0 do
                    avail_x := (Random.int 13)+1;
                    avail_y := (Random.int 13)+1;
                    if((StringMap.mem (string_of_int(!avail_x) ^ "," ^ string_of_int(!avail_y)) !pointMap) = false) then    
                        r :=0;
                done; 
                Point({x=(!avail_x); y=(!avail_y)}) ,env
        else
            raise (Failure ("No available space."));

    (* built-in function print(DATATYPE) *)
    | Call("print", [e]) ->
            let v, env = eval env e in
                (if getType v = "int" then
                    print_endline (string_of_int (getInt v))
                else if getType v = "string" then
                    print_endline (getString v)
                else if getType v = "bool" then
                    print_endline (string_of_bool (getBool v))
                else if getType v = "point" then
                    print_endline ("(" ^ string_of_int (getPoint v).x  ^ " , " ^ string_of_int (getPoint v).y ^ ")")
                else
                    print_endline(getType v));
          Int(0), env      
    
    | Call(f, actuals) -> (* check *)
        let fdecl =
            try NameMap.find f func_decls
            with Not_found -> raise (Failure ("Undefined function: " ^ f))
        in
        let actuals, env = List.fold_left
            (fun (actuals, env) actual ->
            let v, env = eval env actual in v :: actuals, env)
            ([], env) actuals
        in
        let (locals, globals) = env in
        try
            let globals = call fdecl (List.rev actuals) globals
            in Bool false, (locals, globals)
        with ReturnException(v, globals) -> v, (locals, globals)
    in
    (* Execute a statement and return an updated environment *)
    let rec exec env = function
        Block(stmts) -> List.fold_left exec env stmts
        | Expr(e) -> let _, env = eval env e in env
        | If(e, s1, s2) ->
            let v, env = eval env e in
            exec env (if getBool v != false then s1 else s2)
        | While(e, s) ->
            let rec loop env =
                let v, env = eval env e in
                if getBool v != false then loop (exec env s) else env
            in loop env
        | For(e1, e2, e3, s) ->
            let _, env = eval env e1 in
            let rec loop env =
                let v, env = eval env e2 in
                if getBool v != false then
                    let _, env = eval (exec env s) e3 in
                    loop env
                else
                    env
            in loop env
        | Return(e) ->
            let v, (locals, globals) = eval env e in
                if getType v = fdecl.rettype then
                    raise (ReturnException(v, globals))
                else 
                    raise (Failure ("Function " ^ fdecl.fname ^ " returns " ^ getType v ^ " instead of " ^ fdecl.rettype))
    in (* done with below *)
    (* call: enter the function: bind actual values to formal args *)
    let locals =
        try List.fold_left2
            (fun locals formal actual ->
            NameMap.add formal.paramname actual locals)
        NameMap.empty fdecl.formals actuals
        with Invalid_argument(_) ->
            raise (Failure ("Wrong number of arguments to: " ^ fdecl.fname))
    in
    let locals = List.fold_left (* Set local variables to 0 *)
        (fun locals local -> NameMap.add local.varname (init local.vartype) locals)
        locals fdecl.locals
    in (* Execute each statement; return updated global symbol table *)
        snd (List.fold_left exec (locals, globals) fdecl.body)
    
    (* run: set global variables to 0; find and run "main" *)
    in let globals = List.fold_left
        (fun globals vdecl -> NameMap.add vdecl.varname (init vdecl.vartype) globals) (* vdecl is the identifier, "X" *)
        NameMap.empty vars
    in try
        call (NameMap.find "main" func_decls) [] globals
    with Not_found ->
        raise (Failure ("Did not find the main() function"))
